package top.lcm889.oj.offer.按数据结构分类.链表;

import java.util.LinkedList;

/**
 * @author Coder-lcm
 * @date 2021/2/5
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 * 解题思路，快慢指针，
 *      快指针一开始就比慢指针多走n+1，之后就是步进为1,当快指针走完慢指针就到了倒数n位了
 */
public class T19_删除链表的倒数第N个节点 {
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null){
            return null;
        }
        ListNode origin = new ListNode(-1);
        origin.next = head;
        ListNode slow = origin;
        ListNode fast = origin;
        //先让快指针指向n+1位置
        for (int i = 0; i < n+1; i++) {
            fast = fast.next;
        }
        while (fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        //删除倒数第N个节点
        slow.next = slow.next.next;

        return origin.next;
    }

    public static void main(String[] args) {
//        ListNode listNode =
//                new ListNode(22,
//                        new ListNode(13,
//                                new ListNode(331,
//                                        new ListNode(213,
//                                                new ListNode(331,
//                                                        new ListNode(13,
//                                                                new ListNode(22)))))));
//        System.out.println(listNode.next.next.next.next.next.val);
//        removeNthFromEnd(listNode, 2);
//        System.out.println(listNode.next.next.next.next.next.val);

        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.get(1);
    }

}
